package org.example.t0601;

/**
 * 二分查找
 */
public class MidFind {

     static volatile  int [] array = new int[]{1,2,3,4,5,6,7,8,9,10};
    public static void main(String[] args) {

        int index = midFind(9,0,array.length-1);
        System.out.print(index + " ");
        index = midFind2(2);
        System.out.print(index);


    }

    /**
     * while实现
     *
     * @param key
     * @return
     */
    private static int midFind2(int key){
        int index = - 1;
        int lower = 0 ;
        int high = array.length -1;
        while(lower <= high){
         int mid = (lower + high) /2;
         if(array[mid] == key){
             index = mid;
             break;
         }
         if(array[mid] > key){
             high = mid -1;
         }else{
             lower = mid + 1;
         }
        }
        return index;
    }

    /**
     * 递归实现
     * @param key
     * @param lower
     * @param high
     * @return
     */
    private static int midFind(int key,int lower,int high){
        int index = - 1;

        int mid = (lower + high) /2;
        if(array[mid] == key){
            index = mid;
        }
        if(array[mid] < key){
            index = midFind(key,mid+1,high);
        }
        if(array[mid] > key){
            index = midFind(key,lower,mid -1);
        }
        return index;

    }


}
